Graph / Spanning tree (Bibtex)

P471: Enumeration of all spanning trees in a graph

Input:

A graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

Comment:

This paper shows an equation for computing the set of spanning trees in $G$.

Reference:

[Percival1953] (Bibtex)

P490: Enumerate all spanning trees in an input graph

Input:

A graph $G$

Output:

All spanning trees in $G$

Complexity:

Comment:

Reference:

[MacWilliams1958] (Bibtex)

P472: Enumeration of all spanning trees in a graph

Input:

A graph $G=(V, E)$.

Output:

All spanning trees in $G$.

Complexity:

Comment:

Reference:

[Fujisawa1959] (Bibtex)

P491: Enumerate all spanning trees in a graph

Input:

A graph $G$

Output:

All spanning trees in $G$

Complexity:

Comment:

Also multitrees

Reference:

[Watanabe1960] (Bibtex)

P391: Enumeration of all spanning trees in a graph

Input:

A graph $G$.

Output:

All spanning trees in $G$.

Complexity:

Comment:

Reference:

[Hakimi1961] (Bibtex)

P478: Enumeration of all spanning trees in a graph

Input:

A graph $G=(V, E)$.

Output:

All spanning trees in $G$.

Complexity:

Comment:

Reference:

[Bellert1962] (Bibtex)

P1: Enumeration of all spanning trees in a graph

Input:

A graph $G=(V,E)$.

Output:

All spanning trees of $G$.

Complexity:

Comment:

In this paper, 'trees' indicate 'spanning trees'.

Reference:

[Minty1965] (Bibtex)

P383: Enumeration of all spanning trees of a graph

Input:

A graph $G$.

Output:

All spanning trees of $G$.

Complexity:

Comment:

Reference:

[Mayeda1965a] (Bibtex)

P473: Enumeration all spanning trees in a graph

Input:

A graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

Comment:

Reference:

[Piekarski1965] (Bibtex)

P474: Enumeration of all spanning trees in a graph

Input:

A graph $G$.

Output:

All spanning trees in $G$

Complexity:

Comment:

Reference:

[Maxwell1966] (Bibtex)

P476: Enumeration of all cotrees in a graph

Input:

A graph $G = (V, E)$.

Output:

All cotrees in $G$.

Complexity:

Comment:

Cotree: a subgraph $S$ of $G$ such that $S = G - T$ for some spanning tree $T$, where $G - T$ is a subgraph of $G$ that does not contain edges in $T$.

Reference:

[Maxwell1966] (Bibtex)

P477: Enumeration of all 2cotrees in a graph

Input:

A graph $G = (V, E)$.

Output:

All 2cotrees in $G$.

Complexity:

Comment:

A 2cotree is a subgraph with $|E|-|V|$ edges of $G$ which forms cotree of $G$.

Reference:

[Maxwell1966] (Bibtex)

P484: Enumeration of all spanning trees in a graph

Input:

A graph $G$.

Output:

All spanning trees in $G$.

Complexity:

Comment:

Reference:

[McIlroy1969] (Bibtex)

P102: Enumeration of all spanning trees in a graph

Input:

A graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(|E|)$ time per spanning tree with $O(|E|)$ space.

Comment:

Reference:

[Read1975] (Bibtex)

P51: Enumeration of the $k$ smallest weight spanning trees in a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ smallest weight spanning trees in $G$.

Complexity:

$O(k|E|\alpha (|E|,|V|) + |E|\log |E|)$ total time and $O(k + |E|)$ space, $\alpha(\cdot)$ is Tarjan's inverse of Ackermann's function.

Comment:

Reference:

[Gabow1977] (Bibtex)

P52: Enumeration of all spanning trees in a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The all spanning trees in $G$ in order.

Complexity:

$O(N|V|)$ total time and $O(N + |E|)$ space, $N$ is the number of spanning trees in $G$.

Comment:

Reference:

[Gabow1977] (Bibtex)

P67: Enumeration of all spanning trees in an undirected graph

Input:

An undirected graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(|V| + |E| + |V|N)$ total time and $O(|V| + |E|)$ space.

Comment:

$N$ is the number of spanning trees in $G$.

Reference:

[Gabow1978] (Bibtex)

P68: Enumeration of all spanning trees in a directed graph

Input:

A directed graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(|V| + |E| + |E|N)$ total time and $O(|V| + |E|)$ space.

Comment:

$N$ is the number of spanning trees in $G$.

Reference:

[Gabow1978] (Bibtex)

P55: Enumeration of the $k$ smallest weight spanning trees in a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ smallest weight spanning trees in $G$.

Complexity:

$O(k|E| + \min (|V|^2 ,|E|\log \log |V|))$ total time and $O(k + |E|)$ space

Comment:

Reference:

[Katoh1981] (Bibtex)

P370: Enumeration of all spanning trees in an undirected graph

Input:

An undirected graph $G$.

Output:

All spanning trees in $G$.

Complexity:

Comment:

They analized Char's enumeration algorithm.

Reference:

[Jayakumar1984] (Bibtex)

P483: Enumeration of all spanning trees in a graph

Input:

A graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

Comment:

[Mai1984] proposes a parallel method for the enumeration.

Reference:

[Mai1984] (Bibtex)

P53: Enumeration of the $k$ smallest weight spanning trees in a graph in increasing order

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ smallest weight spanning trees in $G$.

Complexity:

$O(|E|\log\log_{(2+|E|/|V|)} n + k^2\sqrt{|E|})$ total time and $O(|E| + k\sqrt{|E|})$ space.

Comment:

Reference:

[Frederickson1985] (Bibtex)

P54: Enumeration of the $k$ smallest weight spanning trees in a planar graph in increasing order

Input:

A planar graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ smallest weight spanning trees in $G$.

Complexity:

$O(|V| + k^2(\log |V|)^2)$ total time and $O(|V| + k(\log |V|)^2)$ space.

Comment:

Reference:

[Frederickson1985] (Bibtex)

P361: Enumeration of all undirected minimum spanning trees in an undirected graph

Input:

An undirected graph $G = (V, E)$.

Output:

All undirected minimum spanning trees in $G$.

Complexity:

$O(|E|\log \beta(|E|, |V|))$ total time.

Comment:

$\beta(|E|, |V|) = \min\{i | \log^{(i)}|V| \le |E|/|N|\}$.

Reference:

[Gabow1986a] (Bibtex)

P362: Enumeration of all directed minimum spanning trees in an directed graph

Input:

A directed graph $G = (V, E)$.

Output:

All directed minimum spanning trees in $G$.

Complexity:

$O(|V|\log \beta(|E|, |V|))$ total time.

Comment:

$\beta(|E|, |V|) = \min\{i | \log^{(i)}|V| \le |E|/|N|\}$.

Reference:

[Gabow1986a] (Bibtex)

P445: Enumeration of all spanning trees in a graph

Input:

A graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(|V| + |E| + N|V|)$ total time with $O(|V|^2)$ space, where $N$ is the number of solutions.

Comment:

Polynomial amortized time.

Reference:

[Winter1986] (Bibtex)

P73: Enumeration of all spanning tree in a graph

Input:

A graph $G = (V, E)$.

Output:

All spanning tree of $G$.

Complexity:

$O(|V|+|E|+N)$ total time and $O(|V||E|)$ space.

Comment:

$N$ is the number of spanning trees in $G$.

Reference:

[Kapoor1991] (Bibtex)

P74: Enumeration of all spanning tree in an weighted graph

Input:

An weighted graph $G = (V, E)$.

Output:

All spanning tree of $G$ in increasing order of weight.

Complexity:

$O(N\log |V|+|V||E|)$ total time and $O(N + |V|^2|E|)$ space.

Comment:

$N$ is the number of spanning trees in $G$.

Reference:

[Kapoor1991] (Bibtex)

P75: Enumeration of all spanning tree in a directed graph

Input:

A directed graph $G = (V, E)$.

Output:

All spanning tree of $G$.

Complexity:

$O(N|V|+|V|^3)$ total time and $O(|V|^2)$ space.

Comment:

$N$ is the number of spanning trees in $G$.

Reference:

[Kapoor1991] (Bibtex)

P47: Enumeration of the $k$ best spanning trees in a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ best spanning trees of $G$.

Complexity:

$O(m\log\beta(|E|, |V|) + k^2)$ total time.

Comment:

$\beta(|E|, |V|) = \min \{\log^{(i)}|V| \le |E|/|V|\}$.

Reference:

[Eppstein1992] (Bibtex)

P48: Enumeration of the $k$ best spanning trees in a planar graph

Input:

A planar graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ best spanning trees of $G$.

Complexity:

$O(n + k^2)$ total time

Comment:

Reference:

[Eppstein1992] (Bibtex)

P88: Generation of the $k$-th minimum spanning tree in a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$-th minimum spanning tree of $G$.

Complexity:

$O((|V||E|)^{k-1})$ time.

Comment:

Reference:

[Mayr1992] (Bibtex)

P110: Enumeration of all spanning trees

Input:

A graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(N + |V| + |E|)$ total time and $O(|V||E|)$ space.

Comment:

$N$ is the number of spanning trees in $G$.

Reference:

[Shioura1995] (Bibtex)

P300: Enumeration of all spanning trees in a directed graph

Input:

A directed graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

INCORRECT: $O(N \log |V| + |V|^2\alpha(V, V) + |V||E|)$

Comment:

$\alpha$: the inverse Ackermann's function. [KR2000] gives this result is wrong.

Reference:

[Hariharan1995] (Bibtex)

P446: Enumeration of all spanning trees in an undirected graph

Input:

An undirected graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(|V| + |E| + N)$ total time with $O(|V||E|)$ space, where $N$ is the number of solutions.

Comment:

Constant amortized time.

Reference:

[Kapoor1995] (Bibtex)

P447: Enumeration of all spanning trees in an undirected and weighted graph in increasing order.

Input:

An undirected and weighted graph $G = (V, E)$.

Output:

All spanning trees in $G$ in increasing order.

Complexity:

$O(N \log (|V|) + |V||E|)$ total time and $O(|V|^2|E|)$ space, where $N$ is the number of solutions.

Comment:

Polynomial amortized time.

Reference:

[Kapoor1995] (Bibtex)

P115: Enumeration of all spanning trees in a directed graph

Input:

A directed graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(|E|+ND(|V|, |E|))$ total time and $O(|E|+DS(|V|, |E|))$ space.

Comment:

$D(|V|, |E|)$ and $DS(|V|, |E|)$ are the time and space complexities of the data structure for updating the minimum spanning tree in an undirected graph with $|V|$ vertices and $|E|$ edges. Here $N$ denotes the number of directed spanning trees in $G$.

Reference:

[Uno1996] (Bibtex)

P15: Enumeration of all spanning trees in a graph

Input:

A graph $G=(V,E)$.

Output:

All spanning trees included in $G$.

Complexity:

$O(N+|V|+|E|)$ total time and $O(|V|+|E|)$ space.

Comment:

$N$ = number of spanning trees in $G$.

Reference:

[Shioura1997] (Bibtex)

P59: Enumeration of the $k$ smallest weight spanning trees in a graph

Input:

A graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ smallest weight spanning trees in $G$.

Complexity:

$O(m \log \log* n + k \min(n, k)^{1/2})$ total time, or a randomized version taking $O(m + k \min(n, k)^{1/2})$ total time.

Comment:

Reference:

[Eppstein1997] (Bibtex)

P83: Enumeration of all spanning trees in a graph

Input:

A graph $G = (V, E)$.

Output:

All spanning trees in $G$.

Complexity:

$O(|V| + |E| + \tau|V|)$ time and $O(|V| + |E|)$ space (depth first manner) or $O(\tau|V| + |E|)$ space (breadth first manner).

Comment:

By using breadth first manner, the proposed algorithm can be used in a parallel computer.

Reference:

[Matsui1997] (Bibtex)

P84: Enumeration of all spanning trees in a graph in non-decreasing order

Input:

A graph $G = (V, E)$.

Output:

All spanning trees in $G$ in non-decreasing order.

Complexity:

$O(|V| + |E| + \tau|V|)$ time and $O(\tau|V| + |E|)$ space.

Comment:

Using breadth first manner.

Reference:

[Matsui1997] (Bibtex)

P120: Enumeration of all directed spanning trees in a directed graph

Input:

A directed graph $G = (V, E)$.

Output:

All directed spanning trees in $G$.

Complexity:

$O(|E| \log |V| + |V| + N \log^2 |V|)$ total time and $O(|E| + |V|)$ space.

Comment:

$N$ is the number of directed spanning trees.

Reference:

[Uno1998a] (Bibtex)

P485: Enumeration of all spanning trees in a directed graph

Input:

A directed graph $G = (V, E)$.

Output:

All directed spanning trees in $G$.

Complexity:

$O(N|V| + |V|^3)$ total time and $O(|V|^2)$ space.

Comment:

$N$: the number of solutions.

Reference:

[Kapoor2000] (Bibtex)

P285: Enumeration of all spanning trees of an weighted graph in order of increasing cost

Input:

An weighted graph $G = (V, E)$.

Output:

All spanning trees of $G$ in order of increasing cost.

Complexity:

$O(N|E|\log |E| + N^2)$ total time and $O(N|E|)$ space.

Comment:

$N$ is the number of spanning trees of $G$.

Reference:

[Sorensen2005] (Bibtex)

P214: Enumeration of all the minimum spanning trees in a graph

Input:

An weighted graph $G = (V, E)$.

Output:

All the minimum spanning trees in $G$.

Complexity:

$O(N|E|\log|V|)$ total time and $O(|E|)$ space.

Comment:

$N$ is the number of the minimum spanning trees in $G$.

Reference:

[Yamada2010] (Bibtex)